package com.example.slidingwindow;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
 *  （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
 *  返回 A 中好子数组的数目。
 *
 *  示例 1：
 * 输入：A = [1,2,1,2,3], K = 2
 * 输出：7
 * 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
 *
 *  示例 2：
 * 输入：A = [1,2,1,3,4], K = 3
 * 输出：3
 * 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
 */
public class Leetcode992_SubarraysWithKDistinct {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 2, 3};
        int k = 2;

        nums = new int[] {10, 2, 1, 3, 4};
        k = 3;
        System.out.println(new Solution().subarraysWithKDistinct(nums, k));
    }

    static class Solution {
        /**
         * 解法二:滑动窗口
         * 用一个map盛装窗口里面的元素(key为数组里的元素,v为元素对应的次数)
         *
         * 初始化将数组的前k个元素装入map中
         * left代表窗口的左边界,right代表窗口的右边界
         *
         * 当范围内不同整数数量小于k，right向后移动一位
         *      当范围内不同整数数量大于k，left向后移动一位
         *      当范围内不同整数数量等于k，临时变量left2从left开始不断向右移动尝试(尝试后需要恢复)，
         *         直到不同整数数量<K (在尝试过程中，结果result进行累加)
         *
         * @param nums
         * @param k
         * @return
         */
        private int subarraysWithKDistinct2(int[] nums, int k) {
            int result = 0;
            Map<Integer, Integer> map = new HashMap();
            int left = 0, right = 0;
            while (right < nums.length) {
                //该位置整数放入map中，如果第一次出现value为1，不是第一次出现则原value+1
                map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
                while (map.size() > k) { //数量超过K个，left指向下一个位置,map中left对应元素次数-1
                    int tmp = map.get(nums[left]);
                    if (tmp > 1) { // 当map的nums[left]的数量大于1时,对应元素个数--
                        map.put(nums[left], tmp - 1);
                    } else { // 当map的nums[left]的数量等于1时,删除该元素
                        map.remove(nums[left]);
                    }
                    left++;
                }
                int left2 = left;//用于尝试计算删除左边几个元素仍能保持数量为K
                while (map.size() == k) {//数量刚好为K个，需要验证下左侧有哪些排除后还能满足K个，则总结果中加1
                    result++;
                    if (map.get(nums[left2]) > 1) {//出现次数>1的可以进行移除尝试
                        map.put(nums[left2], map.get(nums[left2]) - 1);//该数字出现次数-1
                        left2++;//left2右移一位置
                    } else {//某元素次数不大于一，停止尝试
                        break;
                    }
                }
                // 将尝试删除的元素再在map中 恢复,这些数字接下来的right可能还能凑成K个
                for (int i = left; i < left2; i++) {
                    map.put(nums[i], map.get(nums[i]) + 1);//该数字出现次数+1
                }

                right++;
            }
            return result;
        }

        /**
         * 暴力法(超时)
         * 先得到每个子数组，然后用将子数组放入set中，判断set的size是否为k
         * @param nums
         * @param k
         * @return
         */
        private int subarraysWithKDistinct1(int[] nums, int k) {
            // 1,2,1,2,3
            if (k > nums.length) return 0;
            int res = 0;
            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            for (int i = 0; i < nums.length; i++) {
                Set<Integer> set = new HashSet<>(k);
                for (int j = i + k - 1; j < nums.length; j++) {
                    List<Integer> tmp = list.subList(i, j + 1);
                    set.addAll(tmp);
                    if (set.size() == k) res++;
                    else if (set.size() > k) break;
                }
            }

            return res;
        }

        public int subarraysWithKDistinct(int[] nums, int k) {
            return subarraysWithKDistinct2(nums, k);
        }
    }
}
